#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef int ElemType;
typedef struct
{
    ElemType *data;
    int size;
}Stable;


void init_stable(Stable &st,int length)
{
    st.size=length;
    st.data=(ElemType*)malloc(sizeof(ElemType)*length);
    //往数组中填入随机数
    srand(time(NULL));
    for(int i=0; i<length; i++)
    {
        st.data[i]=rand()%100;  //生成0~99的随机数
    }
}

//打印数组
void print_stable(Stable st)
{
    for(int i=0; i< st.size ; i++)
    {
        printf("%3d",st.data[i]);
    }
    printf("\n");
}

void swap(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}

#define SIZE 10
void merge(int *A,int low,int high,int mid)
{
    static int B[SIZE];
    int i,j,k;
    for(i=low; i <= high ;i++)  //将A的数据存放在B中
    {
        B[i]=A[i];
    }
    k=low;
    for(i=low,j=mid+1; i<=mid && j<=high; k++)
    {
        if(B[i] < B[j])
        {
            A[k]=B[i++];
        }
        else
        {
            A[k]=B[j++];
        }
    }
    while(i<=mid)
    {
        A[k++]=B[i++];
    }
    while(j<=high)
    {
        A[k++]=B[j++];
    }
}


//归并排序
void merge_sort(int* a,int low,int high)
{
    if(low< high)
    {
        int mid=(low+high)/2;
        merge_sort(a,low,mid);         //拆分
        merge_sort(a,mid+1,high); //拆分
        merge(a,low,high,mid);  //归并
    }
}


int main() {

    Stable st;
    init_stable(st,SIZE);
    print_stable(st);
    merge_sort(st.data,0,st.size-1);
    print_stable(st);
    return 0;
}


